#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 2e5 + 5;

/*
 cin >> N >> K;
 dp[i][j][k]
 i : the first i cakes
 j : select j cakes
 k : 0bit odd or even flag on how many cakes use a
   : 1bit odd or even flag on how many cakes use b
   : 2bit odd or even flag on how many cakes use c
 dp[i + 1][j][k] = dp[i][j][k] when no use i + 1
                 = dp[i][j - 1][k ^ 1] when use i + 1 as a
                 = dp[i][j - 1][k ^ 2] when use i + 1 as b
                 = dp[i][j - 1][k ^ 4] when use i + 1 as b

 what we need is dp[N][K * 2][0]
 we sort the data on it's max value from greater to less.
 as we want dp[N][K * 2][0] as large as possible,
 if i - j > 3, that means we have 4 or more cake unselected,
 but we could select one more pair obviously.
 once we turn j to i - j, j will be in range [0, 3];
 j means the number of cake unselected.
 when i >= N * 2, we need at most 3 more cakes.
 j means the number of cake needed.
 */
int n, m;
struct Node {
  int a, b, c;
  bool operator<(Node x) const { return max({a, b, c}) > max({x.a, x.b, x.c}); }
} v[N];
ll dp[N][4][8];
ll solve() {
  cin >> n >> m;
  rep(i, 1, n) cin >> v[i].a >> v[i].b >> v[i].c;
  sort(v + 1, v + n + 1);
  rep(j, 0, 3) rep(k, 0, 7) dp[0][j][k] = -1e18;
  dp[0][0][0] = 0;
  rep(i, 1, n) {
    rep(j, 0, 3) rep(k, 0, 7) dp[i][j][k] = -1e18;
    rep(j, 0, 3) rep(k, 0, 7) {  // prev state
      {                          // not selected
        int nj = j;
        if (i <= m * 2) nj++;
        if (nj <= 3) dp[i][nj][k] = max(dp[i][nj][k], dp[i - 1][j][k]);
      }
      {
        int x[3] = {v[i].a, v[i].b, v[i].c};
        rep(t, 0, 2) {
          int nj = j, nk = k ^ (1 << t);
          if (i > m * 2) nj--;
          if (nj >= 0)
            dp[i][nj][nk] = max(dp[i][nj][nk], dp[i - 1][j][k] + x[t]);
        }
      }
    }
  }
  return dp[n][0][0];
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) cout << solve() << endl;
  return 0;
}